package kyssion.introductionToAlgorithms.chapter_02;

/**
 * 逆序对值得就是在任意 i<j && s[i]>s[j] 这种情况
 * 思想就是使用递归的思想, 逆序对就是左边的数量+右面的数量+ 左边和右边比较的数量
 */
public class Alorithms004_2_4_逆序对 {
    public static void main(String[] args) {
        System.out.println(new Alorithms004_2_4_逆序对().ans(
                new int[]{
                        2, 3, 8, 6, 1
                }
        ));
    }


    public int ans(int[] s) {
        return ans(s, 0, s.length - 1);
    }

    public int ans(int[] s, int start, int end) {
        if (start >= end) {
            return 0;
        }
        //start 0 end 1 midle 0
        int midle = (start + end) >> 1;
        int all = ans(s, start, midle) + ans(s, midle + 1, end);
        int n1 = midle - start + 1;
        int n2 = end - midle;
        int[] left = new int[n1 + 1];
        int[] right = new int[n2 + 1];
        left[left.length - 1] = Integer.MAX_VALUE;
        right[right.length - 1] = Integer.MAX_VALUE;
        n1 = 0;
        n2 = 0;
        for (int a = start; a <= end; a++) {
            if (left[n1] <= right[n2]) {
                s[a] = left[n1];
                n1++;
            } else {
                s[a] = right[n2];
                all++;
                n2++;
            }
        }
        return all;
    }
}
